The present application relates generally to a method for calculating the distance between two points. The method is particularly useful to the field of navigation systems wherein the accurate and efficient calculation of distances is required.
Navigation systems are available for vehicles (such as automobiles, trucks, buses, etc.) that travel on roads. These in-vehicle navigation systems provide end users (such as drivers and/or passengers of the vehicles in which the navigation systems are installed) with various useful navigation features. For example, some navigation systems are able to determine an optimum route to be traveled by roads between locations in a geographic region. Using input from an end user and optionally from equipment that can determine one""s physical location (such as a GPS system), programming in the navigation system can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation system may then provide the end user with information about the optimum route in the form of instructions that identify the driving maneuvers required to be taken by the end user to travel from the starting location to the destination location. The instructions may take the form of visual and/or audio instructions that are provided along the way as the end user is travelling the route.
On computer displays that are part of the navigation system hardware, some navigation systems are able to show detailed maps highlighting routes to destinations, the types of maneuvers to be taken along various locations along the routes, the location of certain types of establishments and/or features, etc.
In order to provide these types of features, navigation systems use geographic data. The geographic data may be in the form of one or more databases that include data that represent physical features in a geographic region. The geographic databases include data representing the roads and intersections in a geographic region and also include information relating to the represented roads and intersections, such as turn restrictions at intersections, speed limits along the roads, street name of various roads, address ranges along the roads, etc.
Although navigation systems provide many useful and important features, there continues to be room for improvements in these features. One such area in which there is room for improvement is to use a simplified method of determining the distance between two points accurately and consistently. Difficulties arise in calculating the distance between two points because the earth is not spherical in shape, but instead has an ellipsoidal geometry upon which the navigation databases are based.
Conventional distance calculation techniques include utilizing geodetic formulas that can provide an accurate distance calculation between two points. For example, certain data representing roads and intersections may be expressed in angular units in the WGS84 ellipsoidal coordinates system. Given the latitude and longitude of two points (xcfx861, xcex1), and (xcfx862, xcex2), accuracy in distance of the order of a few millimeters for a line length as long as 200 kilometers can be obtained using the equations 1-12 listed below, and which can be found in the following publication: Geometric Geodesy I, Richard H. Rapp, The Ohio State University, Apr. 1991, pp. 114-115. Equation 12 yields the desired distance between two points after evaluating different quantities as shown in equations 1-11. The notation xe2x80x9caxe2x80x9d refers to the semi-major axis of the ellipsoid, while notation xe2x80x9cexe2x80x9d refers to the eccentricity of the ellipsoid, wherein the remainder of the notations are self-explanatory, with es, A, B, C, W, E, F and D in equations 8, 9 and 10 being intermediate quantities present in the following equations and D in equation representing distance between points.                               e          s          2                =                              e            2                                1            -                          e              2                                                          (        1        )                                A        =                                            1              +                              (                                                      e                    s                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      cos                    4                                    ⁢                                      φ                    1                                                  )                                      ⁢                          xe2x80x83                                                          (        2        )                                B        =                                            1              +                              (                                                      e                    s                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      cos                    4                                    ⁢                                      φ                    2                                                  )                                      ⁢                          xe2x80x83                                                          (        3        )                                C        =                              1            +                          (                              e                s                2                            ⁢                              xe2x80x83                                                                        (        4        )                                w        =                              A            ⁡                          (                                                λ                  2                                -                                  λ                  1                                            )                                2                                    (        5        )                                          Δ          ⁢                      xe2x80x83                    ⁢          φ                =                              φ            2                    -                      φ            1                                              (        6        )                                          Δ          ⁢                      xe2x80x83                    ⁢          λ                =                              λ            2                    -                      λ            1                                              (        7        )                                D        =                                            Δ              ⁢                              xe2x80x83                            ⁢              φ                                      2              ⁢                              xe2x80x83                            ⁢              B                                ⁡                      [                          1              +                                                                    3                    ⁢                                          xe2x80x83                                        ⁢                                          e                      s                      2                                                                            4                    ⁢                                          xe2x80x83                                        ⁢                                          B                      2                                                                      ⁢                                  xe2x80x83                                ⁢                Δ                ⁢                                  xe2x80x83                                ⁢                φ                ⁢                                  xe2x80x83                                ⁢                                  sin                  ⁡                                      (                                                                  2                        ⁢                                                  xe2x80x83                                                ⁢                                                  φ                          1                                                                    +                                                                        2                          3                                                ⁢                                                  xe2x80x83                                                ⁢                        Δ                        ⁢                                                  xe2x80x83                                                ⁢                        φ                                                              )                                                                        ]                                              (        8        )                                E        =                  sin          ⁢                      xe2x80x83                    ⁢                      (            D            )                    ⁢                      xe2x80x83                    ⁢          cos          ⁢                      xe2x80x83                    ⁢                      (            w            )                                              (        9        )                                F        =                              1            A                    ⁢          sin          ⁢                      xe2x80x83                    ⁢                                    (              w              )                        ⁢                          xe2x80x83                        [                                          B                ⁢                                  xe2x80x83                                ⁢                cos                ⁢                                  xe2x80x83                                ⁢                                  φ                  1                                ⁢                cos                ⁢                                  xe2x80x83                                ⁢                D                            -                              sin                ⁢                                  xe2x80x83                                ⁢                                  φ                  1                                ⁢                sin                ⁢                                  xe2x80x83                                ⁢                D                                      ]                                              (        10        )                                          sin          ⁢                      xe2x80x83                    ⁢                      σ            2                          =                                            E              2                        +                          F              2                                                          (        11        )                                D        =                              a            ⁢                          xe2x80x83                        ⁢            C            ⁢                          xe2x80x83                        ⁢            σ                                B            2                                              (        12        )            
As shown above, the equations 1-12 require the evaluation of many non-linear mathematical functions to compute the distance between points. It may not be feasible to perform the evaluation of these non-linear mathematical functions repeatedly where the latitude and longitude of points are constantly changing in certain applications, such as in navigation systems. Also, it is typically not necessary to calculate the distance between points within a few millimeters of accuracy in such applications. Instead, the only requirement is that the distance should be sufficiently accurate for navigation system applications, and that the calculation of such distance should be efficient.
For efficiency, it is necessary to reduce the use of non-linear mathematical functions to the extent possible. As the distances to be determined in conventional navigational system applications are typically not very long, the use of simple formulas and the Pythagorean theorem have been and can be used and still maintain the required level of efficiency and accuracy. Such simple formulas are given below in equations 13-15, although there are certain drawbacks to using these equations as well, which will be discussed below.
DE=N cos xcfx86xcex94xcexxe2x80x83xe2x80x83(13) 
DN=Mxcex94xcfx86xe2x80x83xe2x80x83(14) 
D={square root over (DE2+DNN2)}xe2x80x83xe2x80x83(15) 
wherein                     φ        =                                                            φ                1                            +                              φ                2                                      2                    ⁢                      xe2x80x83                    ⁢                      (                          mean              ⁢                              xe2x80x83                            ⁢              latitude                        )                                              (        16        )                                N        =                  a                                    1              -                                                e                  2                                ⁢                                  sin                  2                                ⁢                φ                                                                        (        17        )                                M        =                              a            ⁡                          (                              1                -                                  e                  2                                            )                                                                          (                                  1                  -                                                            e                      2                                        ⁢                                          sin                      2                                        ⁢                    φ                                                  )                            3                                                          (        18        )            
DE and DN are east and north components of the distance D between the two points (xcfx861,xcex1), and (xcfx862,xcex2), xcex94xcfx86 is the difference in the latitude given in equation 6 above, and xcex94xcex is the difference in the longitude given in equation 7 above. The prime vertical radius of curvature (N) and the meridian radius of curvature (M) are obtained from equations 17 and 18 and, as a result, it is assumed that the earth has an ellipsoidal geometry for the latitude and longitude values in the above formulas. This is required because the latitude and longitude values for a given set of points are based upon the earth having an ellipsoidal geometry. Evaluations of radii of curvature for prime vertical (N) and meridian (M) therefore are performed for the given points in the above formulas. Again, the notation xe2x80x9caxe2x80x9d refers to the semi-major axis of the ellipsoid, while notation xe2x80x9cexe2x80x9d refers to the eccentricity of the ellipsoid. The prime vertical radius of curvature (N) and the meridian radius of curvature (M) are a function of latitude, and their variations from 0 to 90 degrees is shown in FIG. 1. As a result, equations 13 and 14 cannot be replaced with a model of the earth having a spherical geometry. Moreover, as shown in equation 13, an evaluation for cosine also has to be done, as its value is necessary to determine the east component of the distance between the two points. These values are needed every time the latitude coordinate changes, and a floating-point operation is required to compute these quantities, which is a very time consuming operation that must be performed in the computer of the navigation system a large number of times.
Accordingly, it would be desirable to have a method for calculating the distance between two points for use in navigation system that overcomes the disadvantages described above.
In order to provide an improved method of calculating the distance between two points for use in a navigation system that overcomes the above-stated disadvantages, one embodiment of the invention provides a method for calculating a distance between a first point and a second point using linear interpolation. The first point and the second point are located between a first latitude and a second latitude. An interpolated prime vertical radius of curvature value for a point between the first point and the second point is calculated based on a predetermined first prime vertical radius of curvature value for the first latitude and a second predetermined prime vertical radius of curvature value for the second latitude. An interpolated meridian radius of curvature value for the point between the first point and the second point is calculated based on a predetermined first meridian radius of curvature value for the first latitude and a second predetermined meridian radius of curvature value for the second latitude. Finally, an interpolated cosine value for the point between the first point and the second point is calculated based on a predetermined value representing a cosine of the first latitude and a predetermined value representing a cosine of the second latitude. The interpolated prime vertical radius of curvature value, the interpolated meridian radius of curvature value, and the interpolated cosine value can then be used in linear equations to determine the distance between the two points. This method eliminates the evaluation of non-linear functions thereby increasing efficiency and also maintaining accuracy.
Another embodiment of the invention provides a computer readable medium including a program for calculating a distance between a first point and a second point using linear interpolation. The first point and the second point are located between a first latitude and a second latitude. The program includes computer readable program code that calculates an interpolated prime vertical radius of curvature value for a point between the first point and the second point based on a first prime vertical radius of curvature value for the first latitude and a second prime vertical radius of curvature value for the second latitude. The program also includes computer readable program code that calculates an interpolated meridian radius of curvature value for the point between the first point and the second point based on a first meridian radius of curvature value for the first latitude and a second meridian radius of curvature value for the second latitude. In addition, the program includes computer readable program code that calculates an interpolated cosine value for the point between the first point and the second point based on a value representing a cosine of the first latitude and a value representing a cosine of the second latitude. Finally, the program includes computer readable program code that calculates the distance between the first point and the second point based on the interpolated prime vertical radius of curvature value, the interpolated meridian radius of curvature value, and the interpolated cosine value.
The invention provides the foregoing and other features, and the advantages of the invention will become further apparent from the following detailed description of the presently preferred embodiments, read in conjunction with the accompanying drawings. The detailed description and drawings are merely illustrative of the invention and do not limit the scope of the invention, which is defined by the appended claims and equivalents thereof.